#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <math.h>
using namespace std;
/**
 * @brief
 * no ordered
 * 2 <= nums.length <= 10^4
 * 1 <= nums[i] <= 10^4
 *
 */
class Solution
{
public:
    /**
     * @brief O(N^2)
     *  47 / 49 test cases passed.
     * 	Time Limit Exceeded
     * @param nums
     * @return vector<int>
     */
    vector<int> findErrorNums(vector<int> nums)
    {
        int dup = -1, missing = -1;
        int size = nums.size();
        // search all the numbers from 1 to n
        for (int i = 1; i <= size; i++)
        {
            int count = 0;
            // search nums 0-size
            for (int j = 0; j < size; j++)
            {
                if (i == nums[j])
                {
                    count++;
                }
            }
            if (count == 2)
            {
                dup = i;
            }
            else if (count == 0)
            {
                missing = i;
            }
            /**
             * @brief
             * missing>0 find missing
             *
             */
            if (dup > 0 && missing > 0)
            {
                break;
            }
        }
        return {dup, missing};
    }

    /**
     * @brief sorted
     * O(NlogN)
     *
     * @param nums
     * @return vector<int>
     */
    vector<int> findErrorNums_1(vector<int> nums)
    {
        sort(nums.begin(), nums.end());
        int size = nums.size();
        int dup = -1, missing = 1;
        for (int i = 1; i < size; i++)
        {
            if (nums[i] == nums[i - 1])
            {
                dup = nums[i];
            }
            else if (nums[i] > nums[i - 1] + 1)
            {
                missing = nums[i - 1] + 1;
            }
        }
        return {dup, nums[size - 1] != size ? size : missing};
    }

    vector<int> findErrorNums_2(vector<int> nums)
    {

        int size = nums.size();
        int dup = -1, missing = 1;
        unordered_map<int, int> ans;
        for (int n : nums)
        {
            unordered_map<int, int>::iterator iter = ans.find(n);
            ans.emplace(n, iter == ans.end() ? 1 : iter->second += 1);
        }
        for (int i = 1; i <= size; i++)
        {
            unordered_map<int, int>::iterator iter = ans.find(i);
            if (iter != ans.end())
            {
                if (iter->second == 2)
                {
                    dup = iter->first;
                }
            }
            else
            {
                missing = i;
            }
        }
        return {dup, missing};
    }

    vector<int> findErrorNums_3(vector<int> nums)
    {
        int size = nums.size();
        int dup = -1, missing = 1;
        vector<int> ans(size + 1, 0);
        for (int n : nums)
        {
            ans[n] += 1;
        }

        for (int i = 0; i < size + 1; i++)
        {
            if (1 == ans[i])
            {
                continue;
            }
            else if (2 == ans[i])
            {
                dup = i;
            }
            else if (0 == ans[i])
            {
                missing = i;
            }
        }
        return {dup, missing};
    }

    vector<int> findErrorNums_4(vector<int> nums)
    {
        int size = nums.size();
        int dup = -1, missing = 1;
        for (int n : nums)
        {
            if (nums[abs(n) - 1] < 0)
            {
                dup = abs(n);
            }
            else
            {
                nums[abs(n) - 1] *= -1;
            }
        }
        for (int i = 1; i < size; i++)
        {
            if (nums[i] > 0)
            {
                missing = i + 1;
            }
        }
        return {dup, missing};
    }
    vector<int> findErrorNums_5(vector<int> nums)
    {
        vector<int> n;
        int size = nums.size();
        int dup = -1, missing = 1;
        for (int n : nums)
        {
            nums[n % (size + 1) - 1] += size + 1;
        }

        for (int i = 0; i < size; i++)
        {
            int count = nums[i] / (size + 1);
            if (count == 2)
            {
                dup = i + 1;
            }
            else if (count == 0)
            {
                missing = i + 1;
            }
        }

        return {dup, missing};
    }

    vector<int> findErrorNums_6(vector<int> nums)
    {
        /** Assume m is the missing and d is the duplicate element
         diff= m-d;
         squareDiff= m^2-d^2;
         sum=m+d= squareDiff/diff
         =>sum    = (m+d)(m-d)/(m-d);
         now m=(sum+diff)2;
         and d= (sum-diff)2;
        **/
        int diff = 0;
        int sqaureDiff = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            /**
            The order doesnot matter. keep adding the 1 to n and
            simultaneously subracting  corresponding array element.
            Use i+1 to get 1 to n  since i is the index number which is zero based.
            **/
            diff += (i + 1) - nums[i];
            /** squareDiff is also calculated in the same way as diff is calculated. **/
            sqaureDiff += (i + 1) * (i + 1) - nums[i] * nums[i];
        }
        int sum = sqaureDiff / diff;
        return {(sum - diff) / 2, (sum + diff) / 2};
    }

    vector<int> findErrorNums_7(vector<int> nums)
    {
        int size = nums.size();
        vector<int> p(size, 0);
        for (int n : nums)
        {
            p[n - 1]++;
        }
        int dup = 0, missing = 0;
        for (int i = 0; i < size; i++)
        {
            if (p[i] == 2)
            {
                dup = i + 1;
            }
            if (p[i] == 0)
            {
                missing = i + 1;
            }
        }
        return {dup, missing};
    }

    vector<int> findErrorNums_8(vector<int> nums)
    {
        int xor1 = nums[0];
        int setb;
        int i;
        int x = 0;
        int y = 0;
        int n = nums.size();
        // 1-size
        for (int i = 1; i < n; i++)
        {
            xor1 ^= nums[i];
        }
        for (int i = 1; i <= n; i++)
        {
            xor1 ^= i;
        }
        setb = xor1 & ~(xor1 - 1);
        for (int i = 0; i < n; i++)
        {
            if (nums[i] & setb)
                x ^= nums[i];
            else
                y ^= nums[i];
        }
        for (int i = 1; i <= n; i++)
        {
            if (i & setb)
                x ^= i;
            else
                y ^= i;
        }
        int c = 0;
        for (int num : nums)
        {
            if (num == x)
                c++;
        }
        if (c == 0)
            return {y, x};
        return {x, y};
    }
};

int main(int argc, char const *argv[])
{
    Solution s;
    /**
     * @brief
     * [3,2,3,4,6,5] 3,1
     *
     */
    vector<int> res = s.findErrorNums_8({3, 2, 3, 4, 6, 5});
    for (int r : res)
    {
        cout << r << ",";
    }
    cout << endl;
    return 0;
}
